package writtenTraining.day44;

import java.util.*;

/**
 * day44:(1)排序：最小差值
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求最小差值
     * @param a int整型一维数组 数组a
     * @return int整型
     */
    public int minDifference (int[] a) {
        // 排序
        Arrays.sort(a);
        int len = a.length;
        long ret = 0x3f3f3f3f3f3f3f3fL;
        for(int i = 1; i < len; i++) {
            ret = Math.min(Math.abs((long)a[i]-(long)a[i-1]),ret);
        }

        return (int)ret;
    }
}

/**
 * day44(2):dfs：kotori和素因子
 */


 class Main2 {
    public static Set<Integer> set;
    public static int n , ret ;
    public static void main(String[] args) {
//         深度优先遍历
//         输入数据
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        int[] nums = new int[n];

        for(int i = 0; i < n; i++) {
            nums[i] = in.nextInt();
        }

        set = new HashSet<>();
        int INF = 0x3f3f3f3f;
        ret = INF;
        dfs(0,nums);

        if(ret == INF) {
            System.out.println(-1);
        } else {
            System.out.println(ret);
        }
    }

    public static void dfs(int pos,int[] nums) {
//         递归出口
        if(pos == n) {
            return;
        }

        for(int j = 2; j <= nums[pos]; j++) {
            if(check(j) && !set.contains(j)
                    && nums[pos] % j == 0) {
                set.add(j);
                dfs(pos + 1, nums);
                if (set.size() == n) {
                    int sum = 0;
                    for(int num : set) {
                        sum += num;
                    }
                    ret = Math.min(ret,sum);
                }
                //  恢复现场
                set.remove(j);
            }
        }


    }

    public static boolean check(int num) {
        for(int i = 2 ; i <= Math.sqrt(num); i++) {
            if(num % i == 0) {
                return false;
            }
        }

        return true;
    }
}


/**
 * day44(3):动态规划 + 最长递增子序列：dd爱科学1.0（时间复杂度过高!!!）
 */


 class Main {
    public static void main(String[] args) {
//         动态规划 + 最长递增子序列
        // 输入数据
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        char[] chs = in.next().toCharArray();

//         创建dp
        int[] dp = new int[n];

//         初始化
        Arrays.fill(dp,1);

//         填表
        int ret = -0x3f3f3f3f;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < i; j++) {
                if(chs[i] > chs[j]) {
                    dp[i] = Math.max(dp[i],dp[j] + 1);
                }
            }
            ret = Math.max(dp[i],ret);
        }

//         返回值
        System.out.println(n - ret);
    }
}


/**
 * day44(3):最长递增子序列 + 贪心 + 二分：dd爱科学1.0
 */


class Main4 {
    public static void main(String[] args) {
//         最长递增子序列 + 贪心 + 二分
        // 输入数据
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        char[] chs = in.next().toCharArray();

        List<Character> list = new ArrayList<>();
        list.add(chs[0]);
        for(int i = 1; i < n; i++) {
            if(chs[i] >= list.get(list.size() - 1)) {
//                 > 就添加
                list.add(chs[i]);
            } else {
                // <= 就二分替换
                int left = 0, right = list.size() - 1;
                while(left < right) {
                    int mid = left + (right - left ) / 2;
                    if(list.get(mid) > chs[i]) {
//                         一定是比这个数 > 才替换
                        right = mid;
                    }  else {
//                         <= 不替换， 给我记住了
                        left = mid + 1;
                    }
                }

//                 我们只需要替换比他大的
//                 即使是想等的也不替换
                list.set(left,chs[i]);
            }
        }


        System.out.println(n - list.size());
    }
}





